package offer.day26;

public class No42FindGreatestSumOfSubArray {
    /*
     * 面试题42：连续子数组的最大和
     * 题目：输入一个整型数组，数组中有正数、负数。
     * 数组中的一个或连续多个整数组成一个子数组。
     * 求所有子数组的和的最大值。
     * 要求时间复杂度为O(n)
     *
     * 思路：设置两个变量：一个记录当前和  一个记录最大和  返回结果为最大和的值
     * 	若当前和<0  则将其设置为当前变量的值
     *  若当前和>=0 则与当前变量的值进行累加
     *  若当前和 > 最大和   则将最大和设置为当前和，变成最大的
     *
     *
     * */
    public static void main(String[] args) {
        No42FindGreatestSumOfSubArray f = new No42FindGreatestSumOfSubArray();
        int[] array = {1,-2,3,10,-4,7,2,-5};
        System.out.println("数组中最大的子数组之和为："+f.FindGreatestSumOfSubArray(array));
    }

    private int FindGreatestSumOfSubArray(int[] array) {
        if(array==null||array.length==0) return Integer.MIN_VALUE;
        int max=array[0];
        int res=array[0];
        for(int i=1;i<array.length;i++){
            if(res<0){
                res=array[i];
            }else{
                res+=array[i];
            }
            max=Math.max(max,res);
        }
        return max;
    }
}
